

/**
 * @author Lukas Koell
 * @author David Medenjak
 * @author Johannes Riedmann
 */
public class ReplaceableTree extends StringTree {

    /**
     * Constructor.
     * @param parent Parent.
     * @param leftchild Left child.
     * @param rightchild Right child.
     * @param label Label of the node.
     */
    public ReplaceableTree(StringTree parent,
            StringTree leftchild, StringTree rightchild, String label) {
        super(parent, leftchild, rightchild, label);
    }
    
    /**
     * Adds an element at first free position by BFS.
     * @param node Element to be added.
     */
    @Override
    public void add(String node) {
        Queue queue = new Queue();
        queue.add(this);
        StringTree element = null;
        while (!queue.isEmpty()) {
            element = queue.next();
            if (element.leftchild == null) {
                element.leftchild = new ReplaceableTree(element, null, null, node);
                return;
            } else {
                queue.add(element.leftchild);
            }
            if (element.rightchild == null) {
                element.rightchild = new ReplaceableTree(element, null, null, node);
                return;
            } else {
                queue.add(element.rightchild);
            }
        }
    }

    /**
     * Replaces subTree on Position position with subTree, generating subtree with toTree() method.
     * @param position Position to replace.
     * @param subTree Subtree to replace with.
     */
    public void replace(String position, String subTree) {
        if (position.contentEquals(notFound)) {
            throw new IllegalArgumentException("No path.");
        }
        String[] path = position.split(" ");
        StringTree precessor = null;
        StringTree element = this;
        for (int i = 0; i < path.length; i++) {
            if (path[i].contentEquals(left)) {
                precessor = element;
                element = element.leftchild;
            } else if (path[i].contentEquals(right)) {
                precessor = element;
                element = element.rightchild;
            } else {
                if (!position.contentEquals("")) {
                    throw new IllegalArgumentException("Path wrong formatted.");
                }
            }
        }

        StringTree newPart = toTree(subTree, precessor, 0);
        if (precessor == null) {
            return;
        }
        if (path[path.length - 1].contentEquals(left)) {
            precessor.leftchild = newPart;
        } else {
            precessor.rightchild = newPart;
        }
    }

    /**
     * Doing some magic... -.-'
     * @param toString Tree.toString() we read in.
     * @param parent Parent node.
     * @param val Depth level we think it should be.
     * @return Tree Structure of replaceable tree nodes.
     */
    protected ReplaceableTree toTree(String toString, StringTree parent, int val) {
        String[] elements = toString.split("\n");
        String name = elements[0];
        String prepart = ""; // Todo "calculate" prepart length, not generating, then counting?...
        /* Generating prepart of expected depth to evaluate toString generated String */
        if (val == 0) {
            prepart = "";
        } else {
            for (int i = 1; i < val; i++) {
                prepart += ws;
            }
            prepart += mark;
        }
        if (prepart.length() > elements[0].length()) {
            return null;
        }
        /* Not in right "depth" */
        if (!prepart.contentEquals(elements[0].substring(0, prepart.length()))) {
            return null;
        }
        name = name.substring(prepart.length());
        ReplaceableTree newLeft = null;
        ReplaceableTree newRight = null;
        /* Enough elements, try if it's a leftchild */
        if (elements.length > 1) {
            newLeft = toTree(toString.substring(elements[0].length() + 1), newLeft, val + 1);
        }
        /* Enough elements, try if it's a rightchild */
        if (elements.length > 2) {
            int skip = elements[0].length() + elements[1].length() + 2;
            /* Due to DFS structure it could also be last element, so loop through until
            the first u find. Not sure if it's in any case correct.
            For normal trees it's working.*/
            for (int i = 2; i < elements.length; i++) {
                if (skip > toString.length()) {
                    continue;
                }
                newRight = toTree(toString.substring(skip), newRight, val + 1);
                if (newRight != null) {
                    break;
                }
                skip += elements[i].length() + 1;
            }
        }
        /* Due to recursive calls this is our new Tree root, with all nodes linked */
        return new ReplaceableTree(parent, newLeft, newRight, name);
    }
}
